package dp;

/**
 * 用动态规划思想求斐波那契数
 * 1、确定dp[i]的含义：第i个斐波那契数
 * 2、递推公式：dp[i]=dp[i-1]+dp[i-2]
 * 3、dp数组初始化：dp[0]=1,dp[1]=1
 * 4、遍历顺序：从前向后
 * 5、【可选】打印dp数组，方便debug
 */
public class Fibonacci {
    public static void main(String[] args) {

    }
    // 压缩版
    public int Fibo(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
    // 非压缩状态版本
    public int Fibo2(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int index = 2; index <= n; index++) {
            dp[index] = dp[index-1] + dp[index-2];
        }
        return dp[n];
    }
}
